//要求空间复杂度O(n)
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0;i < n;++i)
        {
            //遍历数组将在范围[1,n]的数交换到正确数组对应的下标位置，不在范围内的则不交换
            //交换前要进行判断：要交换的两个数是否相等，相等则不交换。避免导致死循环
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i])
            {
                std::swap(nums[nums[i]-1],nums[i]);
            }
        }
        for(int i = 0;i < n;++i)
        {
            if(nums[i] != i+1){
                return i + 1;
            }
        }
        return n + 1;
    }
};